#define  _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cmath>
#include<algorithm> 
#include<queue>
#include<string>
#include<math.h>
#include<stack>
#include<vector>
#include<set>
#include<unordered_set>
#include<unordered_map>
using namespace std;
enum State
{
	exist,
	Empty,
	deleted
};

template <class k, class v>
struct hashdata
{
	pair<k, v> _kv;//记录数据key-value
	State _state = Empty;//记录状态
};

template<class k>
class hashfunc
{
public:
	size_t operator()(const k& key)
	{
		return (size_t)key;
	}
};
template<>
class hashfunc<string>//模板特化
{
public:
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto ch : key)
		{
			hash += ch;
			hash *= 131;
		}
		return hash;
	}
};
template <class k,class v,class hash=hashfunc<k>>//hash是仿函数类型
class hashtable
{
public:
	hashtable()
	{
		_table.resize(__stl_next_prime(0));
		_size = 0;
	}
	bool insert(const pair<k,v>& kv)
	{
		//if (double(_size) / double(_table.size() >= 0.7))//扩容
		//{
		//	unsigned long newsize = __stl_next_prime(_table.size() + 1);
		//	//扩容后要将数据重新映射
		//	vector<hashdata<k, v>> newtable(newsize);
		//	for (int i=0;i<_table.size();i++)
		//	{
		//		if (_table[i]._state == exist)
		//		{
		//			//...
		//		}
		//	}
		//	_table.swap(newtable);
		//}
		if (find(kv.first)) return false;
		if (double(_size) / double(_table.size()) >= 0.7)//扩容
		{
			unsigned long newsize = __stl_next_prime(_table.size() + 1);
			hashtable<k, v, hash> newht;
			newht._table.resize(newsize);
			for (int i = 0; i < _table.size(); i++)
				if (_table[i]._state == exist) newht.insert(_table[i]._kv);
			_table.swap(newht._table);
		}
		size_t hash0 = hs(kv.first) % _table.size();//模size不能模capacity
		size_t i = 1;
		size_t hashi = hash0;
		while (_table[hashi]._state == exist)
		{
			hashi = (hash0 + i) % _table.size();
			i++;
		}
		_table[hashi]._state = exist;
		_table[hashi]._kv = kv;
		_size++;
		return true;
	}
	hashdata<k, v>* find(const k& key)
	{
		size_t hash0 = hs(key) % _table.size();
		size_t hashi = hash0;
		int i = 0;
		while (_table[hashi]._state != Empty)
		{
			if (_table[hashi]._kv.first == key && _table[hashi]._state == exist) return &_table[hashi];
			hashi = (hash0 + i) % _table.size();
			i++;
		}
		return nullptr;
	}
	bool erase(const k& key)
	{
		hashdata<k, v>* cur = find(key);
		if (cur == nullptr) return false;
		cur->_state = deleted;
		return true;
	}
private:
	hash hs;
	vector<hashdata<k, v>> _table;
	size_t _size = 0;
	unsigned long __stl_next_prime(unsigned long n)
	{
		static const int __stl_num_prime = 28;
		static const unsigned long __stl_prime_list[__stl_num_prime] =
		{
			53, 97, 193, 389, 769,
			1543, 3079, 6151, 12289, 24593,
			49157, 98317, 196613, 393241, 786433,
			1572869, 3145739, 6291469, 12582917,25165843,
			50331653, 100663319, 201326611, 402653189,805306457,
			1610612741, 3221225473, 4294967291
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list + __stl_num_prime;
		const unsigned long* pos = lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}
};
void testhash()
{
	hashtable<int, int> hs1;
	hashtable<string, string> hs2;
	for (int i = -10; i < 53; i++)
		hs1.insert({ i,i });
	hs1.insert({ 97,97 });
	cout << hs1.find(97) << endl;
	hs1.erase(97);
	cout << hs1.find(97) << endl;
	hs2.insert({ "erase","删除" });
	hs2.insert({ "find","查找" });
	hs2.insert({ "string","字符串" });
	hs2.insert({ "vector","数组" });
	hs2.erase("string");
	cout << hs2.find("vector") << endl;
	cout << hs2.find("string") << endl;
}
int main()
{
	testhash();
	return 0;
}

